/**
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

 */

import { ListNode } from "../dataClass";

(function () {
    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     val: number
     *     next: ListNode | null
     *     constructor(val?: number, next?: ListNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.next = (next===undefined ? null : next)
     *     }
     * }
     */

    /**
     * @description 遍历栈
     * @param head
     * @returns
     */
    function reverseList(head: ListNode | null): ListNode | null {
        if (!head) return head;
        const stack: ListNode[] = [];
        while (head) {
            stack.push(head);
            head = head.next;
        }
        stack.forEach((s) => console.log(s.val));

        let cur: ListNode | null | undefined = null;
        let ret: ListNode | null | undefined = null;
        while (stack.length) {
            cur = stack.pop();
            cur && !ret && (ret = cur);
            cur && (cur.next = stack[stack.length - 1]);
        }
        cur && (cur.next = null);
        return ret;
    }
})();

(function () {
    /**
     * @description 递归法
     * @param head
     * @returns
     */
    function reverseList(head: ListNode | null): ListNode | null {
        // console.log("head.val: %s", head.val);
        if (!head || !head.next) return head;
        let ret = reverseList(head.next);
        head.next.next = head;
        // console.log("head.val: %s, head.next.val: %s", head.val, head.next.val);
        if (head.next) head.next = null;
        return ret;
    }
})();

(function () {
    /**
     * @description 双指针
     * @param head
     * @returns
     */
    function reverseList(head: ListNode | null): ListNode | null {
        if (!head || !head.next) return head;
        let pre: ListNode | null | undefined = null;
        let cur: ListNode | null | undefined = head;
        while (cur) {
            let tmp: ListNode | null | undefined = cur?.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
})();
